import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-07-30
 * Time: 22:27
 */
public class test2 {
    public String minWindow(String s, String t) {
        if(s.length()<t.length()){
            return "";
        }
        // key是出现的字母，value是出现的次数
        Map<Character,Integer> hash = new HashMap<>();
        int ansL = -1,ansR = -1;
        for(int i=0;i<t.length();i++){
            hash.put(t.charAt(i),hash.getOrDefault(t.charAt(i),0)+1);
        }
        int size = hash.size();
        int left = 0,right = 0;
        while(right<s.length()){
            char c = s.charAt(right);
            if(hash.containsKey(c)){
                hash.put(c,hash.get(c)-1);
                if(hash.get(c)==0){
                    // 一个元素没了，大小就减一
                    size--;
                }
            }
            right++;
            while(size==0){
                // 减完之后窗口就开始移动
                if(ansL==-1 || right-left<ansR-ansL){
                    ansL = left;
                    ansR = right;
                }
                char c1 = s.charAt(left);
                if(hash.containsKey(c1)){
                    // 重新把这个字母加进去
                    hash.put(c1,hash.get(c1)+1);
                    if(hash.get(c1)==1){
                        size++;
                    }
                }
                left++;
            }
        }
        return ansL==-1?"":s.substring(ansL,ansR);
    }
}
